package com.peng.libext

/**
 * LRU：最近最久未使用置换算法
 */
class LRUCache(var capcity:Int = 8) {

    private var cache:HashMap<Int,Node> = hashMapOf() // 数据储存
    private var head:Node?=null // 用于双向链表记录
    private var end:Node?=null

    fun get(key:Int):Int {
        if(cache.containsKey(key)){
            val node = cache[key]
            // 需要将其位置置换到头部
            node?.also {
                remove(it)
                setHeader(it)
            }
            return node?.value?:-1
        }
        return -1
    }

    fun set(key:Int,value:Int){
        if(cache.containsKey(key)){
            // 替换值，然后迁移到head
            val n = cache[key]
            n?.also {
                it.value = value
                remove(n)
                setHeader(n)
            }
        }else{
            val  node = Node(key,value)
            if(cache.size >= capcity){
                // 删除末尾
                end?.let {
                    cache.remove(it.key)
                    remove(it)
                }
            }
            setHeader(node)
            cache[key] = node
        }
    }

    private fun setHeader(n:Node){
        n.next = head
        n.prev = null
        if(head != null){
            head!!.prev = n
        }
        head = n

        if(end == null){
            end = head
        }
    }

    private fun remove(node: Node){
        if(node.prev != null){
            node.prev!!.next = node.next
        }else {
            // node 是head
            head = node.next
        }

        if(node.next != null){
            node.next!!.prev = node.prev
        }else{
            end = node.prev
        }
    }
}


data class Node(var key:Int, var value:Int, var prev:Node ?= null, var next:Node? = null)